Người ta không rõ ngày thành lập thành phố. Khi nước Việt ở phía Bắc Phúc Kiến bị nhà Chu thôn tính năm 306 trước Công nguyên, một nhánh của hoàng gia của nước Việt chạy trốn đến Phúc Kiến và trở thành bộ lạc Mân Việt. (閩越, Minyue). Thành đầu tiên của Phúc Châu được xây dựng năm 202 trước Công nguyên khi Lưu Bang, người sáng lập nhà Hán cho phép Vô Chư (無諸) - vương của Mân Việt đóng đô ở Phúc Châu. Thành được gọi là Dã (冶, Ye) - nghĩa là "Diêm dúa". Tên này bị thay đổi nhiều nhưng thành không bị phá từ năm 202 sau Công nguyên.

Năm 110 trước Công nguyên, nhà Hán thôn tín Mân Việt, Phúc Châu trở thành huyện Dã.

Trong thời nhà Tấn, Tây Hồ và Đông Hồ và một số kênh được đào (năm 282).

Khi nhà Tấn sụp đổ, một làn sóng dân di cư đến Phúc Kiến (năm 308). Trong thời nhà Đường (năm 725), thành phố bắt đầu được gọi là Phúc Châu. Năm 892, khi nhà Đường sụp đổ, nhiều di dân đến Phúc Kiến hơn, họ Vương lập kinh đô Mân quốc (909-947) đóng đô tại Phúc Châu. Tên gọi Phúc Kiến thời này có Mân Nam, sông chảy qua Phúc Châu gọi là Mân Giang. Người ta xây thành vào các năm: 282, 901, 905 và 975 do đó thành phố có nhiều lớp thành, hơn kinh đô Trung Hoa.

Hoàng đế nhà Tống hạ lệnh phá hủy thành năm 978 nhưng lại cho xây lại sau đó. Lần xây thành cuối cùng là 1371. Trong thời Nam Tống, Phúc Châu thịnh vượng, nhiều học giả đến sống và làm việc tại đây, trong đó có Chu Hi - nhà triết học chỉ xếp sau Khổng Tử và nhà thơ Tân Khí Tật (辛棄疾), nhà thơ vĩ đại nhất của thể loại từ. Marco Polo cũng đã đến đây. Đền Hoa Lâm được coi là di sản quốc gia Trung Quốc. Thời kỳ 1405-1433 đội tàu của nhà Minh do Trịnh Hòa lãnh đạo đã xuất phát từ Phúc Châu đi Ấn Độ Dương 7 lần.

Thời nhà Thanh, nơi đây là nha môn của Tổng đốc Mân Chiết, quản lý các tỉnh Phúc Kiến, Chiết Giang và đảo Đài Loan. Cuối thời nhà Thanh nơi đây có Phúc châu thuyền chính cục là cơ quan quản lý hàng hải có quy mô lớn ở vùng duyên hải đông nam. Xưởng đóng tàu Phúc châu nằm ở Mã vĩ nên cũng có tên là xưởng Mã vĩ, một trong những công xưởng lớn nhất Trung Quốc lúc bấy giờ. Khi chiến tranh Trung Pháp xảy ra năm 1884, hải quân Pháp tấn công hạm đội Phúc kiến neo tàu tại đây và làm hạm đội thiệt hại nặng nề. Sau đó xưởng mới lại được xây dựng lại trên nền cũ.

Ngày 8 tháng 11 năm 1911, những người cách mạng khởi nghĩa ở Phúc Châu, sau một đêm đánh nhau trên đường phố, nhà Thanh đầu hàng. Ngày 22 tháng 11 năm 1933, đội quân thứ 19 lập một chính phủ tồn tại trong thời gian ngắn "Trung Hoa Cộng Hòa Quốc" (中華共和國) (khác với Trung Hoa Dân Quốc) ở Phúc Châu nhưng sụp đổ sau đó mấy tháng.

Phúc Châu có sân bay Quốc tế Trường Lạc.